COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	darpa[e86,jmc]	Notes for 1986 proposal
C00004 00003	∂04-Sep-86  0734	SIMPSON@A.ISI.EDU 	Re: proposal    
C00006 00004
C00017 ENDMK
C⊗;
darpa[e86,jmc]	Notes for 1986 proposal

Notes for phone conversation with Amarel and Simpson

1. The formal reasoning work is on a much more solid foundation,
because we have a stronger group than at any time in the past.

Non-monotonic reasoning and its use in formalizing common sense,
especially causality.

Mathematical theory of computation, Talcott thesis and beyond

Connections with qlisp project

ekl + Shankar

1986 sep 3 - discussion with VAL

I suggested that we undertake to make a fragment of general common
sense database.  He thought this might be too ambitious and suggested
undertaking to do a planner based on his current axiomatization
t[1,val].  It seems to me that this is too modest, and also we
don't want to make our effort primarily programming, because there
are plenty of people emphasizing programming.
He may be right that fully developing the formalism for the general
common sense database may be too ambitious.  The problem is to
formulate suitable subgoals.

In any case, it would be good to include in the proposal a discussion
of the problem of the general common sense database.
∂04-Sep-86  0734	SIMPSON@A.ISI.EDU 	Re: proposal    
Received: from A.ISI.EDU by SAIL.STANFORD.EDU with TCP; 4 Sep 86  07:34:42 PDT
Date: 4 Sep 1986 10:33-EDT
Sender: SIMPSON@A.ISI.EDU
Subject: Re: proposal 
From: SIMPSON@A.ISI.EDU
To: JMC@SU-AI.ARPA
Message-ID: <[A.ISI.EDU] 4-Sep-86 10:33:52.SIMPSON>
In-Reply-To: The message of 02 Sep 86  1403 PDT from John McCarthy <JMC@SAIL.STANFORD.EDU>

John: I believe the best course of action is for you to send a
draft of the proposal for our "unofficial" review.  That way if
there are changes necessary they can be included in the
"official" proposal.  The offical proposal will not be a renewal,
but will need to be submitted in response to one of DARPA's broad
agency announcements which solicited computer science research.
See for example the 17 December 1985 issue of the Commerce
Business Daily (page 63) or the 2 May 1986 CBD (page 48).  Both
of these solicitations expire 30 Sept, but there will be new ones
issued for FY87.  -- Bob


	This is a proposal for the continued activity of the Formal
Reasoning Group of the Computer Science Department of Stanford University.
In the next three years the Formal Reasoning Group proposes to concentrate
on the problems of creating a general database of common sense knowledge
as well as continuing its basic research in artificial intelligence,
computational non-monotonic reasoning,
interactive theorem proving and proving that computer programs satisfy
their specifications.  The work will be based on our previous work in
formalization of common sense knowledge by John McCarthy, non-monotonic
reasoning including especially circumscription by McCarthy and Vladimir
Lifschitz, interactive theorem proving including EKL by Jussi Ketonen and
Natarajan Shankar's use of the Boyer-Moore theorem prover, and work in
mathematical theory of computation by McCarthy and more recently by
Carolyn Talcott.  The work in interactive theorem proving will be joined
by Natarajan Shankar.


Common Sense Knowledge and Reasoning Ability

	A central problem of AI is the creation of programs with
common sense knowledge and reasoning ability.  All specialized human
knowledge is embedded in our common sense knowledge and ability.
For example, the expert system MYCIN knows the names of many bacteria
and has many rules that determine what symptoms and test results allow
inferring that a patient is infected by a particular kind of bacteria.
However, the human use of MYCIN involves common sense that the system does
not possess.  Thus it is the doctor and patient who know about events
taking place in time as well as specific facts like the following:

	a. Patients sometimes get sick and consequently don't feel well
and want to get better.

	b. Patients sometimes die, and then they stay dead.  Patients
don't (normally) want to die.

	c. Doctors want to cure their patients and sometimes can.  This
last presumes the more elementary facts that particular patients become
associated with particular doctors.

	As another example, consider a naval expert system that knows
about ships.  Either it or its user needs to know that ships can be
built, persist in time and can be destroyed by accident, scrapping
or by enemy action.  Facts about the goals naval officers and
men form in doing their jobs are also important.

	In common sense knowledge is included general facts such as
that people try to achieve their goals and more specific facts such
as that ships move on the surface of the water except for submarines
that move both on the surface and beneath it.  (Note that an intelligent
program must know that a submarine can't be on the surface and submerged
at the same time.  This is trivial for humans, but it doesn't seem
to be trivial for humans to design a program for which it is trivial).

	Although the importance of common sense ability was recognized
as early as 1958 (see McCarthy 1960), progress in getting computer
programs with common sense has been slow.  The basic problem is that
understanding the general characteristics of common sense knowledge
has proved to be a difficult scientific problem.

	The proposal of (McCarthy 1960) to use mathematical logical
languages and mathematical logical reasoning has proved to be
essentially sound.  However, the reasoning part has had to be
modified to include non-monotonic reasoning (McCarthy 1980, 1986)

	A major symptom of the difficulty is that the knowledge and
reasoning carried out by common sense reasoners up to now has been
very specialized.  Up to now people haven't succeeded in expressing
the common sense knowledge in a way that can be used by programs
in general and not just for a particular purpose.  One reason, in
our opinion, is that context has not been treated properly, and the
non-monotonic reasoning involved in going from one context to another
hasn't yet been formalized.


The Common Sense Database

	We have some new ideas that we believe will make possible
the creation of databases of general common sense knowledge, and
we propose to explore these ideas and develop a sample common
sense database.  The sample database won't cover any large
fraction of common sense knowlege, but what is in it will be
general --- suitable for applications invented after the
knowledge has been put in the database.

	The feasibility of this project depends on recently discovered
tools.  These are the circumscription method of non-monotonic reasoning as
developed by McCarthy, Lifschitz and others and on an idea of McCarthy's
concerning the formal treatment of context.

	The non-monotonic reasoning is required, because of the
``qualification problem'' first identified in [McCarthy and Hayes 1969].
It arises when we attempt to put the conditions under which an
action can be performed into a general purpose database.  For example,
what about the qualification that a river not have a fence down the
middle as a condition for using a boat to cross the river.  On the
one hand, a person constructing the database is unlikely to think
of this qualification, and if he thinks of this one, an ingenious
opponent can think of twenty more.  On the other hand, if it is
left out, programs, unlike a humans, might reason incorrectly when
presented with information that a particular river has a fence down
the middle.  Systems that use circumscription and some other forms
of non-monotonic reasoning can use databases that contain an axiom
asserting that a boat can be used to cross a river unless something
prevents it.  Unless something is known or conjectured that prevents
the use of a boat in a particular instance, the system will conclude
that the boat can be used.  If informed about a fence, it will not
draw this conclusion.

	The second proposal concerns the formalization of the idea
of context and is newer than circumscription.  Propositions are
reified and are asserted with by formulas of the form $holds(p,c)$,
where $p$ is the proposition and $c$ is a context.
There is a partial order $c1 ≤ c2$ among contexts interpreted as
asserting that $c1$ is less general, i.e. has more specific assumptions,
than $c2$.  Thus we will have $c1 ≤ c2 ∧ holds(p,c2) ⊃ holds(p,c1)$.
Different contexts are specific about different things, and there is
no most general context in which nothing is assumed.  There is a
non-monotonic rule asserting that normally something holding in the
more special context also holds in a more general context.
We believe that formalized contexts will permit general databases
that contain implicit assumptions as does human knowledge.  The
reasoning program will be able to transcend any of these assumptions
when there is evidence that this should be done.


Computational Non-monotonic Reasoning